#include <algorithm>
#include <iostream>
#include <vector>

/* 全排列dfs */
void permutation_dfs(const std::vector<int> nums, std::vector<int> &state, std::vector<bool> &visited, std::vector<std::vector<int>> &res)
{
    if (state.size() == nums.size()) {
        // std::for_each(state.cbegin(), state.cend(), [](int num) { std::cout << num << " "; });
        // std::cout << "\n";
        res.push_back(state);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (!visited[i]) {
            state.push_back(nums[i]);
            visited[i] = true;
            permutation_dfs(nums, state, visited, res);
            state.pop_back();
            visited[i] = false;
        }
    }
}

void permutation(const std::vector<int> nums, std::vector<std::vector<int>> &res)
{
    std::vector<int> state;
    std::vector<bool> visited(nums.size(), false);

    permutation_dfs(nums, state, visited, res);
}

int main()
{
    std::vector<int> nums = {1, 2, 3, 4};
    std::vector<std::vector<int>> res;
    permutation(nums, res);

    std::for_each(res.cbegin(), res.cend(), [](std::vector<int> nums) {
        std::for_each(nums.cbegin(), nums.cend(), [](int num) { std::cout << num << " "; });
        std::cout << std::endl;
    });

    return 0;
}